package offer;

public class Solution51 {
    public int reversePairs(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return 0;
        }
        return mergeSort(nums, 0, n - 1, new int[n]);
    }

    int mergeSort(int[] nums, int left, int right, int[] temp) {
        if (left == right) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        int leftPairs = mergeSort(nums, left, mid, temp);
        int rightPairs = mergeSort(nums, mid + 1, right, temp);
        return merge(nums, left, mid, right, temp) + leftPairs + rightPairs;
    }

    int merge(int[] nums, int l, int m, int r, int[] temp) {
        System.arraycopy(nums, l, temp, l, r + 1 - l);
        int i = l, j = m + 1, k = l;
        int ans = 0;
        while (i <= m && j <= r) {
            if (temp[i] <= temp[j]) {
                nums[k++] = temp[i++];
            } else {
                ans += m - i + 1;
                nums[k++] = temp[j++];
            }
        }
        while (i <= m) {
            nums[k++] = temp[i++];
        }
        while (j <= r) {
            nums[k++] = temp[j++];
        }
        return ans;
    }
}
